The present invention concerns computer graphics and particularly the generation of memory addresses for the image memory in a graphics system.
The advance in computer technology has been such that users of workstations and even individual personal computers now routinely have at their command enough computer power to operate many computer applications concurrently. This capability has proven extremely useful because many tasks that a computer can aid a human in performing require that the human user direct his attention concurrently to the results of a number of computer applications. For this reason, "windowing" capabilities have enjoyed significant popularity. In windowing, various subsections of the computer's display screen are allocated to displaying the results of different applications. The allocation occurs dynamically; the user "opens" and "closes" different numbers of windows at different times, so the number and positions of the windows can change within a session. Typically, a user can open a window while retaining a previously used window on the screen. In such a situation, the new window often "overlaps" the old window so that a section of the old window is occluded. Users also can typically "pop" an occluded window to the top of the priority order so that it can be viewed in its entirety. This occludes part of the previously occluding window.
Although the user cannot see an occluded segment, the computer typically must still retain the contents of the occluded segment in some off-screen memory so that it can be recalled when the previously occluded segment should again become visible. For performance reasons, some graphics subsystems provide more of the fast, dedicated image memory than is required to refresh the display. It is desirable to be able to use this excess image memory as off-screen memory.
In the more-sophisticated systems, however, large numbers of windows can be active simultaneously, and large numbers of occluded segments of many different shapes and sizes can thus be created. In such systems, the required storage for occluded segments can exceed the capacity of off-screen memory. When the off-screen-memory capacity has been exceeded, data must be offloaded into some back-up memory, such as system memory or some mass-storage device (e.g., magnetic media), and significant performance penalties are incurred. Since the cost of providing large amounts of off-screen memory is high, the efficiency with which that memory is utilized is a significant design consideration.
Much of the off-screen-memory size requirement results from the fact that the occluded segments come in many shapes and sizes, and because of this variety the occluded segments do not fall into an efficient storage arrangement in the off-screen memory. Computer programs for storing occluded segments therefore usually employ some type of technique for arranging the different-shaped segments in such a manner as to increase the efficiency in the storage process; like the amount of different-sized objects that can fit in a given-sized box, the amount of occluded segments that can be stored in a given-sized memory depends on the way in which they are arranged.
Even the most-efficient arrangement of integral occluded segments within the off-screen memory, however, usually leaves a fairly large amount of that memory unusable. For this reason, workers have employed "tiling" routines, which break each occluded segment into smaller segments, or "tiles." Tiles can be stored more efficiently than the larger occluded segments can be. Unfortunately, the algorithmic delay imposed by tiling can make it too slow a process for some of the more demanding graphics operations.